package demo.DataStrucAndAlgo.Search;

import java.util.ArrayList;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/27-07-27-20:03
 * @Description：demo.DataStrucAndAlgo.Search   二分查找
 */
/*
二分查找（数据是有序的）
    二分查找依赖排序，采用递归完成，
    首先要确定传入数据的中间下标，然后将待查找数据与中间数据对比，
    小于就向左递归查找，大于就向右递归查找。当等于时就找到了。返回数据索引。
    没找到时，通过递归终止条件left>right来返回-1
 */
public class binarySearch {
    public static void main(String[] args) {
        int[] data = {1,2,2,2,3,4};
        System.out.println(binary_Search(data,0,data.length,2));
    }

    /**
     * 二分查找
     * @param data    数据数组
     * @param left    左索引
     * @param right   右索引
     * @param num     待查找数据
     * @return     查找到数据返回索引，反之返回-1
     */
    public static ArrayList<Integer> binary_Search(int[] data, int left, int right, int num) {
        if(left>right){     //已遍历完数据，未找到匹配值，终止递归
            return new ArrayList<>();
        }
        int mid = (left + right)/2;    //二分
        if(num < data[mid]){
            return binary_Search(data,left,mid-1,num);   //向左递归查找
        }else if(num > data[mid]){
            return binary_Search(data,mid+1,right,num);   //向右递归查找
        }else{
            ArrayList<Integer> list = new ArrayList();  //创建动态数组
            int temp = mid-1;
            while(temp>=0 && data[temp] == num ){
                list.add(temp);
                temp--;
            }
            list.add(mid);
            System.out.println(mid);
            temp = mid+1;
            while(temp < data.length && data[temp] == num){
                list.add(temp);
                temp++;
            }
            return list;    //找到了，返回索引
        }
    }
}
